package dataStructures.list;

import java.util.Iterator;

/**
 *
 * Fully Tested: Yes
 * Fully Documented: Yes
 * Created: 2011
 * Last Modified: Nov 16, 2011
 * @author Shimu
 */
public class LinkedListFunction<T extends Comparable<T>> implements Iterable<T> {

    /** The size of the Queue */
    private int size;

    private SinglelyLinkedNode<T> first, last;

    public LinkedListFunction() {
        this.size = 0;
        this.first = null;
        this.last = null;
    }

    public LinkedListFunction(T firstData) {
        this(new SinglelyLinkedNode<T>(firstData));
    }

    public LinkedListFunction(SinglelyLinkedNode<T> firstNode) {
        this.size = 0;
        this.first = firstNode;
        this.last = firstNode;
    }

    public SinglelyLinkedNode<T> getFirst() {
        return this.first;
    }

    /**
     * Adds an item to the front of the LinkedList.
     * @param data
     */
    public void addFirst(T data) {
        SinglelyLinkedNode<T> oldFirst = first;
        first = new SinglelyLinkedNode<T>(data, oldFirst);
        size++;
    }

    /**
     * Adds an item to the back of the LinkedList.
     * @param data
     */
    public final void addLast(T data) {
        SinglelyLinkedNode<T> newNode = new SinglelyLinkedNode<T>(data);
        if (first == null) {
            first = newNode;
            first.next = last;
        } else if (last == null) {
            last = newNode;
            first.next = last;
        } else {
            last.next = newNode;
            last = last.next;
        }
        size++;
    }

    /**
     * Returns and removes an item from the front of the LinkedList.
     * Returns null if the item at the front of the LinkedList is null or
     * if the LinkedList is empty.
     *
     * @return the item at the front of the LinkedList
     */
    public T removeFirst() {
        if (first == null) {
            return null;
        } else {
            T returnData = first.data;
            first = first.next;
            size--;
            if (first == null) {
                last = null;
            }
            return returnData;
        }
    }

    /**
     * Returns true if this LinkedList has no more elements, false otherwise.
     * @return true if this LinkedList is empty.
     */
    public boolean isEmpty() {
        return (size == 0);
    }

    /**
     * Returns the number of elements in this LinkedList.
     * @return the size of this LinkedList.
     */
    public int getSize() {
        return this.size;
    }

    /**
     * Performs merge sort on this SinglelyLinkedList
     */
    public void mergeSort() {
        if (this.size <= 1) {
            return;
        }
        SinglelyLinkedNode<T> firstHalf, temp, secondHalf;

        int iteration;

        firstHalf = this.first;
        for (int increment = 1; increment < this.size / 2; increment *= 2) {

            iteration = this.size / increment / 2;
            for (int i = 0; i < iteration; i++) {
                secondHalf = firstHalf.cut(increment);
                temp = secondHalf.cut(increment);
                merge(firstHalf, secondHalf, temp);
                firstHalf = temp;
            }
        }
    }

    /**
     * Merge the linked list starting at list1Start with the linked list
     * starting at list2Start. Returns the node that points to the start
     * of the newly merged linked list. Merges in place.
     *
     * @param list1Start the start of one linked list
     * @param list2Start the start of another linked list
     * @return the start of the merged linked list
     */
    public SinglelyLinkedNode<T> merge(SinglelyLinkedNode<T> list1Start,
            SinglelyLinkedNode<T> list2Start, SinglelyLinkedNode<T> endOfList) {

        SinglelyLinkedNode<T> returnNodePrev, list1Prev, list1,
                list2, list2Next;
        list1 = list1Start;
        list2 = list2Start;

        returnNodePrev = new SinglelyLinkedNode<T>(null, list1);
        list1Prev = returnNodePrev;

        while (true) {

            if (list2.data.compareTo(list1.data) == -1) {

                list1Prev.next = list2;

                // Store list2.next in a temporary variable
                list2Next = list2.next;

                list2.next = list1;

                if (list2Next == endOfList) {
                    break;
                } else {
                    list1Prev = list2;
                    list2 = list2Next;
                }
            } else {
                if (list1.next == endOfList) {
                    list1.next = list2;
                    break;
                } else {
                    list1Prev = list1;
                    list1 = list1.next;
                }
            }
        }

        return returnNodePrev.next;
    }

    /**
     * Same as merge, except its NOT in place
     */
    private SinglelyLinkedNode<T> merge2(SinglelyLinkedNode<T> list1Start,
            SinglelyLinkedNode<T> list2Start) {
        SinglelyLinkedNode<T> returnNodePrev, mergedListCurrent, list1Current,
                list2Current;
        list1Current = list1Start;
        list2Current = list2Start;

        returnNodePrev = new SinglelyLinkedNode<T>(null);
        mergedListCurrent = returnNodePrev;

        /**
         * 4 cases
         * Case 1 (list1Current greater than or equal to list2Current):
         * list1Current = list1Current.next
         *
         * Case 2 (list2Current less than list1Current):
         *
         *
         * Case 3 (list1Current is null; list1 is empty):
         * Append list2 to the end of merged list
         *
         * Case 4 (list2Current is null; list2 is empty):
         * Append list1 to the end of merged list
         */
        while (true) {
            if (list2Current.data.compareTo(list1Current.data) == -1) {
                mergedListCurrent.next = list2Current;
                list2Current = list2Current.next;
                if (list2Current == null) {
                    mergedListCurrent.next.next = list1Current;
                    break;
                } else {
                    mergedListCurrent.next.next = null;
                }
            } else {
                mergedListCurrent.next = list1Current;
                list1Current = list1Current.next;
                if (list1Current == null) {
                    mergedListCurrent.next.next = list2Current;
                    break;
                } else {
                    mergedListCurrent.next.next = null;
                }
            }

            mergedListCurrent = mergedListCurrent.next;
        }

        return returnNodePrev.next;
    }

    /**
     * Prints the content of this SinglelyLinkedList
     */
    public void printContent() {
        Iterator<T> iterator = this.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }

    /**
     * Returns a SinglelyLinkedList that is a sublist of this
     * SinglelyLinkedList from index 0 to index endIndex - 1.
     *
     * @param endIndex
     * @return a sublist of this list
     */
    //public SinglelyLinkedList<T> getSubList(int endIndex){
    //}
    @Override
    public Iterator<T> iterator() {
        class SinglelyLinkedListIterator implements Iterator<T> {

            private SinglelyLinkedNode<T> current;

            private SinglelyLinkedListIterator() {
                this.current = first;
            }

            @Override
            public boolean hasNext() {
                return (current != null);
            }

            @Override
            public T next() {
                T returnData = current.data;
                current = current.next;
                return returnData;
            }

            @Override
            public void remove() {
            }
        }

        return new SinglelyLinkedListIterator();
    }
}
